Certain embodiments of the present invention relate to navigational route planning. In particular, certain embodiments of the present invention relate to determining a route through a road network.
Route planning devices are well known in the field of navigational instruments. Several algorithms utilized by planning devices calculate the route from one of the source and/or destination locations or from both simultaneously. Conventional planning algorithms operate based on a predefined stored data structure including data indicative of a geographic region containing the source and destination locations.
Some devices implement a straight line approach in determining the distance between source and destination locations. In the straight line approach, the processor creates a straight line from the present location to the final destination and measures that straight line distance. For example, if a desired destination is on a mountain, the straight line distance from a current location might be only six miles. However, if the only available road to that destination is a windy road around the mountain entailing 30 miles of actual driving, the route planning distance calculated by the straight line approach will be inaccurate.
Other devices implement a nodal analysis in which a number of potential paths are determined from a present location to a destination location based on stored data indicative of roadways between nodes. The nodal analysis then examines each potential path and determines an impedance or xe2x80x9ccostxe2x80x9d associated with each path (i.e. a measure of the amount of time or distance required to travel the path). Paths are eliminated based on criteria such as shortest distance, shortest time, lowest cost, or user inputted preferred routes.
However, conventional route planning devices will not find the most efficient route since they do not take into consideration certain factors that affect travel over a particular route. For example, a user may input desired source and destination locations, and request the route that covers the shortest distance. While only one particular route may be the physically shortest distance between source and destination locations, other near-shortest routes may exist that are only slightly longer. The shortest and near-shortest routes include travel along different combinations of roads and travel through unique combinations of road intersections. Each road in the shortest and near-shortest routes has an associated travel speed, representing the speed limit or range at which traffic typically travels over the road. Also, each road in the shortest and near-shortest routes passes through a combination of intersections. The shortest and near-shortest routes may be close in length, while the shortest route may include roads with slower travel speeds and/or more intersections and/or intersections that typically require more time (e.g., stop signs, stop lights, crossing larger/busier highways, turning across traffic onto a new road, etc.) as compared to one or more near-shortest routes.
Conventional route planning devices produce a shortest distance route which includes roads that are selected independent of whether the roads have slower traveling speeds. Conventional route planning devices do not include travel-time information for road intersections, nor account for delays at road intersections when planning a route. Although one route represents the shortest distance, a more efficient route may exist with a slightly longer distance (e.g., a near-shortest distance route). The difference between the length of the shortest distance route and the near-shortest distance route may be insignificant. Consequently, the user may travel for a longer period of time and encounter more traffic delays by taking the shortest distance route.
Conventional route planning devices do not take into consideration travel delays experienced at intersections, such as delays due to stop signs, stop lights, crossing lanes of on-coming traffic, turning onto or off of one-way roads, the angle at which roads intersect when a route turns from one road onto another, and the like. This is not desirable.
Thus, a need has long existed in the industry for a method and apparatus for determining impedance time through a road network that addresses the problems noted above and other problems previously experienced.
Certain embodiments of the present invention relate to a method for estimating an impedance time through a node at an intersection between roads in a roadway network. The method includes identifying characteristic information that describes at least one feature of the intersecting roads. Based on the characteristic information, an impedance time associated with potential delays by traffic traveling through the node is estimated. The characteristic information may include speed information, such as speed categories or speed bands. A speed band identifies a speed range in which traffic travels on the road, and a speed differential between the speed bands of intersecting roads may be determined. Optionally, the characteristic information may include road-type or network routing level information, such as when the roadway network is divided into a hierarchy of road-types. A route level may be assigned to each road intersecting at a node, and a route level differential between the route levels of the roads may be determined. The characteristic information may include intersection angle information and/or cross traffic turn information.
In another embodiment of the present invention, a method is provided for calculating a navigation route between first and second geographic locations through a roadway network of roads that intersect at nodes. A data structure is provided that has data indicative of the roadway network of roads. The data includes feature data indicating traffic characteristics for the roads. Route impedance is calculated for a navigation route through the roadway between the first and second locations based on the feature data. The node impedance is determined for the navigation route where the navigation route intersects other roads. The node impedance may indicate a potential delay that traffic experiences when traveling through a node. The node impedance and route impedance are used to calculate the navigation route. The node and route impedances may be measured in time or distance.
The feature data may include speed information, one-way, and/or intersection angle information. A turn penalty may be assigned when the navigation route crosses on-coming traffic. Optionally, a neighborhood penalty may be added to the node or route impedance when the navigation route travels through residential areas that are not located at the first and second geographic locations. Optionally, an exit/entry ramp penalty may be added to the node or route impedance when the navigation route travels along an exit ramp from a first road directly onto an entry ramp back onto the first road.
In another embodiment of the present invention, a navigation device is provided comprising a memory and processor. The memory at least temporarily stores at least a portion of a data structure having data indicative of a roadway network of roads intersecting at nodes. The data structure includes feature data of traffic characteristics for roads. The processor accesses the memory and calculates a route through the roadway network between geographic locations from the data stored in the data structure. The processor estimates node impedances for intersection nodes, and utilizes the route impedance and node impedance to calculate the route. The feature data may include speed information, road-type information, routing level information, intersection angle information, and/or cross traffic information which is used to calculate node impedance. Optionally, the device may include an input buffer for temporarily storing a portion of the data structure received from an external storage device. In one embodiment, the device includes a display that presents the route to an operator. The device may also comprise a wireless input/output unit used to communicate with an external network and receive a portion of the data structure of a wireless connection with the external network.
In another embodiment of the present invention, a navigation system is provided comprising a storage unit, a route calculation module, and a correction module. The storage unit stores a data structure having data indicative of roads and intersection nodes in a roadway network. The data includes road-type information that classifies roads into a hierarchy of route levels. The route calculation module calculates a planned route between source-and destination locations over the network based on the stored data. The route calculation module may calculate the route based on a shortest distance routing algorithm, and may add a distance penalty to potential routes that include an exit or entrance ramp. The correction module identifies undesirable shortcuts by using the road-type information to avoid traveling from a road of a higher route level to a road of a lower route level. Undesirable shortcuts may be along exit and entrance ramps of a road or through neighborhoods. Optionally, the correction module may include a neighborhood progression module that updates the route to avoid residential roads that are remote from the source and destination locations.
The route calculation module may receive a request from a mobile unit over a network to calculate a route. The request would include source and destination locations, and other use specific information. The route calculation module would access corresponding data structures, such as in a server, plan the route, and return the planned route to the mobile unit. The returned information would include the portion of the roadway network between the source and destination locations. The network may be the internet, a wireless connection and the like.